package com.nanbei.dp;

import java.util.Arrays;

/**
 * @ClassDescription: 最长递增子序列
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/10 11:18
 */
public class LongestIncreasingSubsequence {

    /*
            1       3       6      4       9
            1       13      16     14      19
                            136    134     139
                                           169
                                           1369
                                           149
                                           1349
          （1）     （2）    （3）   （3）   （4）


     */


    public static void main(String[] args) {
      //  System.out.println(lengthOfLIS(new int[]{1, 3, 6, 4, 9}));
     //   System.out.println(lengthOfLIS(new int[]{1, 1, 1, 1, 1}));
      //  System.out.println(lengthOfLIS(new int[]{10,9,2,5,3,7,101,18}));
        System.out.println(lengthOfLIS(new int[]{0,1,0,3,2,3}));
    }

    public static int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        // 字符数组中的每个数字就是数组的一个子序列,所以全部设置默认值为1
        Arrays.fill(dp,1);
/*        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            int dx = dp[i];
            for (int j = 0; j < i; j++) {
                int y = nums[j];
                int dj = dp[j];
                if (x > y){
                    dp[i] = Math.max(dx,dj+1);
                }
            }
        }*/


        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            for (int j = 0; j < i; j++) {
                int y = nums[j];
                if (x > y) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }


        System.out.println(Arrays.toString(dp));
        int max = 0;
        for (int i : dp) {
            max = Math.max(max, i);
        }
        return max;
    }
}
